home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / TEMP / GNU / bison / LookAhead < prev    next >
Text File  |  1995-06-28  |  2KB  |  55 lines
  1. Look-Ahead
  2. Previous: <Algorithm=>Algorithm> * Next: <Shift\/Reduce=>ShiftRedue> * Up: <Algorithm=>Algorithm>
  3.  
  4. #Wrap on
  5. {fH3}Look-Ahead Tokens{f}
  6.  
  7. The Bison parser does {fEmphasis}not{f} always reduce immediately as soon as the
  8. last {fStrong}n{f} tokens and groupings match a rule.  This is because such a
  9. simple strategy is inadequate to handle most languages.  Instead, when a
  10. reduction is possible, the parser sometimes ``looks ahead'' at the next
  11. token in order to decide what to do.
  12.  
  13. When a token is read, it is not immediately shifted; first it becomes the
  14. {fUnderline}look-ahead token{f}, which is not on the stack.  Now the parser can
  15. perform one or more reductions of tokens and groupings on the stack, while
  16. the look-ahead token remains off to the side.  When no more reductions
  17. should take place, the look-ahead token is shifted onto the stack.  This
  18. does not mean that all possible reductions have been done; depending on the
  19. token type of the look-ahead token, some rules may choose to delay their
  20. application.
  21.  
  22. Here is a simple case where look-ahead is needed.  These three rules define
  23. expressions which contain binary addition operators and postfix unary
  24. factorial operators ({fEmphasis}!{f}), and allow parentheses for grouping.
  25.  
  26. #Wrap off
  27. #fCode
  28. expr:     term '+' expr
  29.         | term
  30.         ;
  31.  
  32. term:     '(' expr ')'
  33.         | term '!'
  34.         | NUMBER
  35.         ;
  36. #f
  37. #Wrap on
  38.  
  39. Suppose that the tokens {fEmphasis}1 + 2{f} have been read and shifted; what
  40. should be done?  If the following token is {fEmphasis}){f}, then the first three
  41. tokens must be reduced to form an {fCode}expr{f}.  This is the only valid
  42. course, because shifting the {fEmphasis}){f} would produce a sequence of symbols
  43. {fCode}term ')'{f}, and no rule allows this.
  44.  
  45. If the following token is {fEmphasis}!{f}, then it must be shifted immediately so
  46. that {fEmphasis}2 !{f} can be reduced to make a {fCode}term{f}.  If instead the
  47. parser were to reduce before shifting, {fEmphasis}1 + 2{f} would become an
  48. {fCode}expr{f}.  It would then be impossible to shift the {fEmphasis}!{f} because
  49. doing so would produce on the stack the sequence of symbols {fCode}expr
  50. '!'{f}.  No rule allows that sequence.
  51.  
  52. The current look-ahead token is stored in the variable {fCode}yychar{f}.
  53. \*Note <Action Features=>ActionFeat>: Special Features for Use in Actions.
  54.  
  55.